﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _05_贪心与暴力递归
{
   public class Heap<T> where T : IComparable
   {
      private List<T> _base;
      private IComparer<T> _cmp;
      public int heapSize;

      // 默认大根堆
      private struct HeapDefaultComparator : IComparer<T>
      {
         public int Compare(T x, T y)
         {
            return x.CompareTo(y);
         }
      }

      // 小根堆比较器
      public struct SmallHeapComparator : IComparer<T>
      {
         public int Compare(T x, T y)
         {
            return y.CompareTo(x);
         }
      }

      // 堆内元素交换
      private void Swap(List<T> list, int a, int b)
      {
         T temp = list[a];
         list[a] = list[b];
         list[b] = temp;
      }

      // 堆化
      private void Heapify(int i = 0)
      {
         int left = 2 * i + 1, right = left + 1;
         while (left < heapSize)
         {
            int maxIndex = (
               ((right < heapSize) && (_cmp.Compare(_base[right], _base[left]) > 0)) ?
               right : left);
            maxIndex = (_cmp.Compare(_base[maxIndex], _base[i]) < 0) ? i : maxIndex;
            if (maxIndex == i)
               return;
            Swap(_base, i, maxIndex);
            i = maxIndex;
            left = 2 * i + 1;
            right = left + 1;
         }
      }

      // 堆插入
      private void HeapInsert(T val)
      {
         int i = _base.Count;
         _base.Add(val);
         heapSize++;
         int parent;
         while (i != 0)
         {
            parent = (i - 1) / 2;
            if (_cmp.Compare(_base[parent], _base[i]) < 0)
            {
               Swap(_base, i, parent);
               i = parent;
            }
            else break;
         }
      }

      public Heap()
      {
         _base = new List<T>();
         _cmp = new HeapDefaultComparator();
         heapSize = 0;
      }

      public Heap(IComparer<T> comparer)
      {
         _base = new List<T>();
         _cmp = comparer;
         heapSize = 0;
      }

      public Heap(List<T> list)
      {
         foreach (var item in list)
            HeapInsert(item);
         _cmp = new HeapDefaultComparator();
      }

      public Heap(List<T> list, IComparer<T> comparer)
      {
         foreach (var item in list)
            HeapInsert(item);
         _cmp = comparer;
      }

      public void Push(T val)
      {
         HeapInsert(val);
      }

      public void Pop()
      {
         if (IsEmpty())
            throw new Exception("Heap is empty");
         Swap(_base, 0, heapSize-- - 1);
         Heapify();
      }

      public bool IsEmpty()
      {
         return heapSize == 0;
      }

      public T Front()
      {
         if (IsEmpty())
            throw new Exception("Heap is empty");
         return _base[0];
      }
   }
}
